package hot100;


/*
 * Author：江松
 * Date：2023/4/22 10:20
 *
 在排序数组中查找元素的第一个和最后一个位置
 */

public class Main34 {

    public int left(int[]nums,int target){
        int l=0,r=nums.length-1;
        while(l<=r){
            int mid=l+((r-l)>>1);
            if(nums[mid]<target){
                l=mid+1;
            }else if(nums[mid]>target){
                r=mid-1;
            }else{
                r=mid-1;
            }
        }
        return l;
    }

    public int right(int[]nums,int target){
        int l=0,r=nums.length-1;
        while(l<=r){
            int mid=l+((r-l)>>1);
            if(nums[mid]<target){
                l=mid+1;
            }else if(nums[mid]>target){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return r;
    }

    public int[] searchRange(int[] nums, int target) {
        int l=left(nums,target);
        int r=right(nums,target);
        int res[]=new int[2];
        if(l<0||l>=nums.length||nums[l]!=target)res[0]=-1;
        else res[0]=l;
        if(r<0||r>=nums.length||nums[r]!=target)res[1]=-1;
        else res[1]=r;
        return res;
    }
}
